/*
 * @lc app=leetcode.cn id=37 lang=cpp
 *
 * [37] 解数独
 *
 * https://leetcode.cn/problems/sudoku-solver/description/
 *
 * algorithms
 * Hard (67.50%)
 * Likes:    1301
 * Dislikes: 0
 * Total Accepted:    151K
 * Total Submissions: 223.5K
 * Testcase Example:
 * '[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]'
 *
 * 编写一个程序，通过填充空格来解决数独问题。
 *
 * 数独的解法需 遵循如下规则：
 *
 *
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 *
 *
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 *
 *
 *
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：board =
 * [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
 *
 * 输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
 * 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
 *
 *
 *
 *
 *
 *
 * 提示：
 *
 *
 * board.length == 9
 * board[i].length == 9
 * board[i][j] 是一位数字或者 '.'
 * 题目数据 保证 输入数独仅有一个解
 *
 *
 *
 *
 *
 */

// @lc code=start
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    bool valid;
    void solveSudoku(vector<vector<char>> &board) {
        vector<vector<bool>> board_status(9, vector<bool>(9, false));
        vector<vector<bool>> row(9, vector<bool>(9, false));
        vector<vector<bool>> column(9, vector<bool>(9, false));
        vector<vector<bool>> square(9, vector<bool>(9, false));
        vector<pair<int, int>> spaces;
        valid = false;
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                spaces.push_back({i, j});
                if (board[i][j] != '.') {
                    int digit = board[i][j] - '0';
                    board_status[i][j] = true;
                    int square_index = getSquareIndex(i, j);
                    row[digit - 1][i] = column[digit - 1][j] = square[digit - 1][square_index] = true;
                }
            }
        }
        backtracking(board, board_status, row, column, square, spaces, 0);
    }

    void backtracking(vector<vector<char>> &board, vector<vector<bool>> &board_status, vector<vector<bool>> &row,
                      vector<vector<bool>> &column, vector<vector<bool>> &square, vector<pair<int, int>> spaces, int pos) {
        if (pos == (int)spaces.size()) {
            valid = true;
            return;
        }
        auto [x, y] = spaces[pos];
        if (board_status[x][y]) {
            backtracking(board, board_status, row, column, square, spaces, pos + 1);
            return;
        }
        for (int i = 1; i <= 9 && !valid; ++i) {
            int square_idx = getSquareIndex(x, y);
            if (row[i - 1][x] || column[i - 1][y] || square[i - 1][square_idx]) {
                continue;
            }
            // 修改当前节点
            board[x][y] = '0' + i;
            row[i - 1][x] = column[i - 1][y] = square[i - 1][square_idx] = true;
            // 递归
            backtracking(board, board_status, row, column, square, spaces, pos + 1);
            // 回改
            row[i - 1][x] = column[i - 1][y] = square[i - 1][square_idx] = false;
        }
    }
    // 序号0-8
    int getSquareIndex(int x, int y) {
        if (x <= 2) {
            if (y <= 2) {
                return 0;
            }
            else if (y <= 5) {
                return 1;
            }
            else {
                return 2;
            }
        }
        else if (x <= 5) {
            if (y <= 2) {
                return 3;
            }
            else if (y <= 5) {
                return 4;
            }
            else {
                return 5;
            }
        }
        else {
            if (y <= 2) {
                return 6;
            }
            else if (y <= 5) {
                return 7;
            }
            else {
                return 8;
            }
        }
    }
};
// @lc code=end
